// 2025/2/26
// https://leetcode.cn/problems/median-of-two-sorted-arrays/description/?envType=problem-list-v2&envId=binary-search
// 寻找两个正序数组的中位数

class Solution {
    public:
        int findk(vector<int>& nums1, vector<int>& nums2, int k)
        {
            int m = nums1.size(), n = nums2.size();
            int i = 0, j = 0;
            while(true)
            {
                // nums1元素全被排除
                if(i == m) return nums2[j + k - 1];
                // nums2元素全被排除
                if(j == n) return nums1[i + k - 1];
                // 找出来了
                if(k == 1) return min(nums1[i], nums2[j]);
    
                int index1 = min(m, k / 2 + i) - 1, index2 = min(n, k / 2 + j) - 1;
                if(nums1[index1] >= nums2[index2])
                {
                    k -= index2 + 1 - j;
                    j = index2 + 1;
                }
                else
                {
                    k -= index1 + 1 - i;
                    i = index1 + 1;
                }
            }
        }
    
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int totalLen = nums1.size() + nums2.size();
            if(totalLen % 2 == 1)
            {
                return findk(nums1, nums2, totalLen / 2 + 1);
            }
            else
            {
                return ((float)findk(nums1, nums2, totalLen / 2) + findk(nums1, nums2, totalLen / 2 + 1)) / 2;
            }
        }
    };